<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width,initial-scale=1.0">
        <meta http-equiv="X-UA-Compatible" content="ie=edge,chrome=1">
        <title>215. 数组中的第K个最大元素</title>
    </head>
    <body>
        <section>
            在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
        </section>
        <h1>方法一</h1>
        <pre class="language-JavaScript">
            <code>
                var findKthLargest = function(nums, k) {
                    quickSort(nums, 0, nums.length - 1, k - 1);
                    return nums[k - 1];
                };
    
                function quickSort(arr, left, right, target) {
                    if(left >= right) {
                        return;
                    }
                    let privot = findPrivot(arr, left, right);
    
                    let l = left, r = right;
                    let k = left;
                    while(k >= l && k <= r) {
                        if(arr[k] === privot) {
                            k ++;
                        } else if(arr[k] > privot) {
                            swap(arr, k, l);
                            l ++;
                            k ++;
                        } else {
                            swap(arr, k, r);
                            r --;
                        }
                    }
                    if(target < l) {
                        quickSort(arr, left, l - 1, target);
                    } else if(k > r) {
                        quickSort(arr, r + 1, right, target)
                    }
                }
    
                function swap(arr, i, j) {
                    let temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
    
                function findPrivot(arr, left, right) {
                    let privot = arr[left];
                    if(left + 2 <= right) {
                        if((arr[left + 1]  - privot) * (arr[left + 1] - arr[left + 2]) < 0) {
                            privot = arr[left + 1];
                        } else if((arr[left + 2]  - privot) * (arr[left + 2] - arr[left + 1]) < 0) {
                            privot = arr[left + 2];
                        }
                    }
                    return privot;
                }
            </code>
        </pre>
        <script type="text/html">
            var findKthLargest = function(nums, k) {
                quickSort(nums, 0, nums.length - 1, k - 1);
                return nums[k - 1];
            };

            function quickSort(arr, left, right, target) {
                if(left >= right) {
                    return;
                }
                let privot = findPrivot(arr, left, right);

                let l = left, r = right;
                let k = left;
                while(k >= l && k <= r) {
                    if(arr[k] === privot) {
                        k ++;
                    } else if(arr[k] > privot) {
                        swap(arr, k, l);
                        l ++;
                        k ++;
                    } else {
                        swap(arr, k, r);
                        r --;
                    }
                }
                if(target < l) {
                    quickSort(arr, left, l - 1, target);
                } else if(k > r) {
                    quickSort(arr, r + 1, right, target)
                }
            }

            function swap(arr, i, j) {
                let temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

            function findPrivot(arr, left, right) {
                let privot = arr[left];
                if(left + 2 <= right) {
                    if((arr[left + 1]  - privot) * (arr[left + 1] - arr[left + 2]) < 0) {
                        privot = arr[left + 1];
                    } else if((arr[left + 2]  - privot) * (arr[left + 2] - arr[left + 1]) < 0) {
                        privot = arr[left + 2];
                    }
                }
                return privot;
            }
            console.log(findKthLargest([3,2,1,5,6,4],2))
        </script>
        <script>
            /// 不太对，leetcode上运行不通过
            var findKthLargest = function(nums, k) {
                let minHead = new MinHead();
                for(let i = 0; i < nums.length; i ++) {
                    if(minHead.getSize() < k) {
                        minHead.push(nums[i]);
                    } else {
                        let min = minHead.getMin()
                        if(min < nums[i]) {
                            minHead.modify(nums[i]);
                        }
                    }
                }
                return minHead.getMin();
            };

            class MinHead {
                constructor(k) {
                    this.arr = new Array(k);
                    this.size = 0;
                }
                push(num) {
                    this.arr[this.size] = num;
                    this.size ++;
                    //向上移
                    this.shiftUp(this.size - 1)
                }
                modify(num) {
                    this.arr[0] = num;
                    this.shiftDown(0)
                }
                _parent(n) {
                    return ((n - 1) / 2 ) >> 0;
                }
                _leftLeaf(n) {
                    return 2 * n + 1;
                }
                _rightLeaf(n) {
                    return 2 * n + 2;
                }
                _wrap(i, j) {
                    let temp = this.arr[i];
                    this.arr[i] = this.arr[j];
                    this.arr[j] = temp;
                }
                getSize() {
                    return this.size;
                }
                getMin() {
                    return this.arr[0];
                }
                shiftUp(k) {
                    // if(n === 0) {
                    //     return;
                    // }
                    // let target = n;
                    // let parentNode = this._parent(target);
                    // while(parentNode >= 0 && this.arr[parentNode] > this.arr[target]) {

                    //     this._wrap(parentNode, target);
                    //     target = parentNode;
                    //     if(parentNode === 0) {
                    //         break;
                    //     }
                    //     parentNode = this._parent(parentNode)

                    // }
                    while (k > 0 && this.arr[k] < this.arr[this._parent(k)]) {
                        this._wrap(k, this._parent(k));
                        k = this._parent(k);
                    }
                }
                shiftDown(k) {
                    // if(n >= this.len) {
                    //     return;
                    // }
                    // let target = n;
                    // let node = this._leftLeaf(target);
                    // while(node < this.size && this.arr[node] < this.arr[target]) {
                        
                    //     let rightNode = this._rightLeaf(target);

                    //     if(rightNode < this.size && this.arr[node] > this.arr[rightNode]) {
                    //         node = rightNode;
                    //     }
                    //     this._wrap(node, target);

                    //     target = node;
                    //     node = this._leftLeaf(target);
                    // }
                    while (this._leftLeaf(k) < this.size) {
                        let j = this._leftLeaf(k);
                        // 存在右孩子而且右孩子比左孩子大
                        if (this._rightLeaf(k) < this.size && this.arr[this._rightLeaf(k)] > this.arr[j] ) {
                            j++;
                        }
                        if (this.arr[k] > this.arr[j])
                            return;
                        // 父节点比子节点小，交换位置
                        this._wrap(k, j);
                        // 继续下沉
                        k = j;
                    }
                }
            }

           // console.log(findKthLargest([3,2,1,5,6,4],0))
        </script>
    </body>
</html>